密码学中的模乘算法——巴雷特模乘(Barrett Modular Multiplication)
密码学实践中常常需要处理 的模运算。模运算中当属模乘是最复杂的。蒙哥马利方法(Montgomery Modular Multiplication)是一种经典的快速模乘算法，感兴趣的小伙伴可以点击查看密码学中的模乘算法——蒙哥马利模乘（Montgomery Modular Multiplication）。这里介绍另外一种经典的快速模乘算法，称之为巴雷特方法（Barrett Modular Multiplication）[1]。
直觉
明确这里有待解决的问题，即求解
这里 是一个浮点数。也就是说，如果我们能够以较高精度算得 , 那么求 是显然的。
考虑下面形式的逼近[2]，即寻找这样的整数 , 使得
因此有 。实践中通常取 且 。也就是说仅仅需要正常的乘法，加法和移位操作就可以完成模约减(modular reduction)运算，BarrettReduce算法大致可以描述如下：
上面的直觉有一个关键点没考虑。因为无论如何选取 ,,和目标 总是存在误差。由 可推出：
总之 。为了分析方便，这里要求选择相对大的 使得 。那么，上文中的BarrettReduce算法中的变量 满足：
所以算法的最终输出
完整版的BarrettReduce算法描述如下：
正式叙述
正式叙述的写作思路部分参考[3]，它提供了Barrett算法的Python/Java代码实现。
在实际模约减中，常常遇到的情况是 , 不是 power-of-2 (因为模约减之前的运算是乘法，乘法的结果不会超过)。现在讨论这种情况下如何合理设置参数 和 。根据“直觉”章节的介绍，我们知道 的最小取值为 , 又因为 , 因此有理由选取：
"直觉"章节总结了 ，因此有理由选取：
综上所述，Barrett模约减算法总结如下：
1.选取, 。
2.计算。
3.计算。
4.if :
5. 。
6.return 。
注意当模数固定时（绝大部分应用都是这种情形），算法的第1步只需要做一次即可。因此算法的主要运算是第2步的乘法和 第3步的乘法 。
和蒙哥马利模约减的比较
从计算形式来看，Montgomery方法需要将输入的整数转成“蒙哥马利形式”，最后还需要将结果从蒙哥马利形式转回正常表达，因此Montgomery方法适用于大量,连续的模乘应用，比如RSA的模幂运算；Barrett方法则不需要这种复杂的形式转换，应用的范围更广。
从计算量来看，假定模数 有 bit，那么Barrett需要做一次 的乘法，一次 的乘法；Montgomery需要做两次 的乘法，计算复杂度更优些。
本文参考
[1]Barrett, Paul. "Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor." Advances in Cryptology—CRYPTO’86: Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000.
[2]https://en.wikipedia.org/wiki/Barrett_reduction
[3]https://www.nayuki.io/page/barrett-reduction-algorithm
本文作者：hujwei
知乎链接：https://zhuanlan.zhihu.com/p/621388087
往期推荐
1.笔记分享 | 组队学习密码学（2）——密码学在联邦学习中的应用
2.笔记分享 | 冯登国院士MPC讲座（3）——基于混淆电路方法的安全多方计算协议pFedPT：将prompt学习融入进联邦学习4.密码学中的模乘算法——蒙哥马利模乘（Montgomery Modular Multiplication）